'''
https://leetcode.cn/problems/super-washing-machines/description/
'''

from typing import List

class Solution:
    def findMinMoves(self, machines: List[int]) -> int:
        n = len(machines)
        total = sum(machines)
        if total % n != 0: return -1
        avg = total // n

        ans = 0
        left_sum = 0
        for i in range(n):
            right_sum = total - left_sum - machines[i]
            left = i
            right = n - i - 1
            left_need = left * avg - left_sum
            right_need = right * avg - right_sum

            if left_need > 0 and  right_need > 0:
                bottleneck = left_need + right_need
            else:
                bottleneck = max(abs(left_need), abs(right_need))
            ans = max(ans, bottleneck)
            left_sum += machines[i]
        return ans

machines = [0,3,0]
print(Solution().findMinMoves(machines))